package me.project.offer;

/**
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * <p>
 * <p>
 * Consider the following matrix:
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * <p>
 * Given target = 5, return true.
 * Given target = 20, return false.
 *
 * @author Mcdull
 * @date 2018-6-28
 */
public class Solution04 {
    /**
     * AC
     * O(N+M) + O(1)
     *
     * @param target
     * @param matrix
     * @return
     */
    public boolean Find(int target, int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;
        int rows = matrix.length;//行
        int cols = matrix[0].length;//列

        int r = 0, c = cols - 1;//从右上角开始
        while (r <= rows - 1 && c >= 0) {
            if (target == matrix[r][c]) {
                return true;
            } else if (target > matrix[r][c]) {
                r++;
            } else {
                c--;
            }
        }
        return false;
    }

    /**
     * Java heap space
     * O(N*M) + O(1)
     *
     * @param target
     * @param matrix
     * @return
     */
    public boolean Find2(int target, int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;
        int a = matrix.length;
        int b = matrix[0].length;
        StringBuilder sb;
        sb = new StringBuilder();
        for (int i = 0; i < b; b++) {
            for (int j = 0; j < a; j++) {
                sb.append(matrix[i][j]).append(",");
            }
        }
        return sb.indexOf(target + ",") != -1;
    }
}
